1. Field of the Invention
This invention relates to signal processing with reduced combinatorial complexity, and to various aspects thereof, i.e. to an automated method, an apparatus and a computer program for implementing such processing. It is particularly (but not exclusively) relevant to reduction of combinatorial complexity in radar target tracking.
2. Description of the Art
Combinatorial complexity (or combinatorial explosion) in signal processing is well known. It arises in a situation where there is an evolving set of phenomena for which at intervals parameters are determined (e.g. measurements are made) which incompletely characterise the phenomena. At each individual interval it is not possible to associate parameters with respective phenomena unambiguously, in which case from interval to interval it is important to make hypothetical associations between phenomena and parameters, and derive respective probabilities for these associations expressing their likelihood of being correct. This enables errors in monitoring evolution of phenomena to be reduced by the smoothing effects of determination over multiple intervals. Phenomena may evolve in any dimension or set of dimensions, e.g. space and/or time. The difficulty is that the number of hypothetical phenomenon/parameter associations in a real scenario, i.e. the number of possible combinations, increases exponentially with the number of phenomena, far exceeding the capacity of a conventional computer to deal with it in real time. In other words combinatorial complexity is too great for conventional signal processing.
An example of monitoring an evolving set of physical phenomena is referred to as tracking, and is known for a variety of applications. Tracking is commonly implemented in the case of spatial motion, e.g. radar monitoring of civil aircraft in flight. It may also be used in signal processing (e.g. speech recognition) for choosing between possible candidate points on a trajectory in a phase space and associated with a signal evolving with time. In the case of radar monitoring, the evolving set of physical phenomena is a set of radar target tracks and the parameters which are determined are measurements of target range and bearing made at regular time intervals by a radar system. The signal processing problem in this case is to determine assignments of successive sets of radar measurements to evolving target tracks and determine associated weights or probabilities indicating degree of assignment validity. The possibility must be also be taken into account that the measurements may include noise, false negatives (undetected targets) and false positives (wrongful detection of targets).
In IEEE Transactions on Aerospace and Electronic Systems, volume 31(1), pages 458-468, January 1995, B Zhou and N Bose disclose an algorithm for data association in multi-target tracking, i.e. tracking a number of targets using a number of measurements and hypothetical tracks. Given initial target positions and measurements of target positions (e.g. radar range and bearing measurements), the general approach of this and other prior art techniques is to derive hypothetical extensions for each track and accept, reject or average them on the basis of their probability. However, as Zhou et al. point out, unfortunately the number of feasible hypothetical track extensions grows very rapidly with increasing numbers of targets and measurements, much more so than can be accommodated in real-time signal processing at the present time. In consequence, research on multi-target tracking has given a lot of attention to improving computational efficiency, i.e. reducing the processing burden associated with hypothetical track extensions. The Zhou et al. approach is to compute a posteriori probabilities of the origins of measurements in the joint probabilistic data association filter. This results in a technique suitable for parallel processing.
U.S. Pat. No. 5,537,119 also discloses a technique for multi-target tracking. It again describes the basic approach of using measurements on multiple targets to derive possible tracks and associated probabilities or cost functions. This patent describes the basic technique of determining observation assignments by minimising a summation subject to constraints, the summation being of products of a track cost function, track/observation indices and a track observation assignment. It states that the only known method of solving this is by an approach referred to as “branch and bound”, which introduces a workload unsuitable for real-time operation. Methods are discussed for reducing complexity by discarding potential tracks on the basis of probability, and also the iterative use of Lagrangian relaxation to reduce the dimensionality of the problem and identify which assignments to discard.
In “Multitarget-Multisensor Tracking: Principles and Techniques”, 1995, Y Bar-Shalom and X-R Li disclose an approach to multi-target tracking. A respective set of measurements to locate tracks is made at each of a series of time instants. An individual target track is expressed as a set of hypothetical tracks each with a respective occurrence probability. Each hypothetical track is associated with a respective sub-set of the measurement set at any instant, and has association probabilities for respective measurements in the sub-set. Each association probability expresses the likelihood of the respective measurement and track being associated with one another. An important part of the multi-target tracking procedure is to generate an updated set of hypothetical tracks in response to input of each successive set of measurements.